The human leukocyte antigen (“HLA”) region on chromosome 6 is highly polymorphic. In particular, the sequence of this region varies from person to person. See, e.g., Consolandi et al., Human Immunology 2003, 64:168. Approximately 1,750 different sequence variants or “alleles” have been identified to date at the HLA locus. There are many biological implications of the high degree of heterogeneity of this region. For example, the presence or absence of a given HLA allele or “HLA type” may predict the presence or absence of diseases, dictate the course of treatment for a patient, or, most notably, determine the compatibility of a potential transplant recipient with the donor organ or bone marrow.
One of the approaches to finding the right allele is to design a microarray experiment that provides the allele as an answer. In fact, HLA typing by sequence hybridization with sequence-specific oligonucleotide probes (“SSOP”) is currently practiced by the National Marrow Donor Program (“NMDP”) for donor-recipient matching, along with more traditional serological-based methods. See, e.g., Cao et al., Reviews in Immunogenetics 1999, 1:177; and Noreen et al., Tissue Antigens 2001, 57:221. In a format that is popular in many current test methods, the DNA samples to be classified are amplified with locus-specific primers, and spotted onto the microarray chips, thus resulting in multiple copies of identical chips; each chip is then hybridized to a different probe. See Balazs et al., Human Immunology 2001, 62:850; Consolandi et al., Human Immunology 2003, 64:168. This methodology necessitates a new design process every time a new set of patient samples must be classified. Moreover, most of the currently used techniques are both time-consuming and lack optimality.
The system, process, storage medium and software arrangement according to one exemplary embodiment of present application provides a graph model on the set of potential probes in which the HLA typing problem is formulated mathematically as an optimization problem. According to the present application, it is also possible to utilize an algorithm for solving the optimization problem. The processes of translating the typing problem to the graph model and translating the optimizing probe set back to an experimental design for HLA typing are also described. Extensions of the graph model to more detailed physical models are discussed as well.